package com.yusong.algorithm.link;

/**
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 *
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 *
 */
public class OddEven328 {

    public static void main(String[] args) {
        int[] data = {1,2,3,4,5};
        ListNode node = ListNodeUtil.create(data);

        OddEven328 demo = new OddEven328();
        node = demo.oddEvenListOffical(node);
        ListNodeUtil.printNode(node);
    }


    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode firstEven = null;
        ListNode lastOdd = head;
        ListNode node = head;
        ListNode preOdd = head;
        ListNode preEven = null;
        int index = 0;
        while (node.next != null){
            node = node.next;
            if(index %2 == 1){
                preOdd.next = node;
                preOdd = node;
                lastOdd = node;
            }else{
                if(null == firstEven){
                    firstEven = node;
                }
                if(preEven != null){
                    preEven.next = node;
                }
                preEven = node;
            }
            index++;
        }
        preEven.next = null;
        lastOdd.next = firstEven;
        return head;
    }

    /**
     * 官方解题思路
     */
    public ListNode oddEvenListOffical(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head;
        ListNode even = evenHead;
        while (even != null){
            //保证Odd不为空
            if(even.next != null){
                odd.next = even.next;
                odd = odd.next;

                even.next = even.next.next;
                even = even.next;
            }else {
                even.next = null;
                even = null;
            }
        }
        odd.next = evenHead;
        return head;
    }

}


/*
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
 */